/*
 * SmartCam master processor library
 * Coprocessor mapping evaluation.
 *
 * NOTE: Assumes transports under DMA (no load on the processor)
 */

#define _ISOC99_SOURCE

#include <math.h>
#include <log.h>
#include "globals.h"
#include "mapping.h"
#include "evaluate.h"
#include "evaldeps.h"
#include "settings.h"

extern table_t scm_procs, scm_ops, scm_streams, /* owned, indexed */
               scm_links;                       /* owned */

double scEvlMapping(double iop)
{
  double diff;
  int iter=0;

  if (scs_mapper.evaluator == SC_EVL_UNRELATED)
    return scEvlMappingUnrelated();
  else if (scs_mapper.evaluator == SC_EVL_DEPENDENT)
    return scEvlMappingDeps(iop);

  scEvlInit();

  scEvlPropagate(SCM_MIN);
  scEvlPropagate(SCM_MAX);

  do
  {
    scEvlBackupFractions();

    scEvlBoundMaxUsage();
    scEvlPropagate(SCM_MAX);
    scEvlBoundMinUsage();
    scEvlPropagate(SCM_MIN);

    diff = scEvlCompareFractionsToBackup();
    lprintf(STREAM(scl.crawl), "L_inf of the risidual is %7.5f", diff);
    iter++;
  } while (diff > SC_EVL_EPSILON);    

  lprintf(STREAM(scl.debug), "Sum of root minimum flow is %7.5f after %d iterations",
	  scEvlRootMin(), iter);

  return scEvlRootMin();
}

void scEvlInit(void)
{
  int id=-1, id2=-1;
  scm_proc_t *p;
  scm_op_t *o;
  scm_stream_t *s;
  char buf[PATH_MAX];

  /* Unmapped operations and streams start with maximum usage */
  strcpy(buf, "[ ");
  while (tblget(&scm_ops, id = tblgetnexti(&scm_ops, id), &o))
  {
    if (o->processor) sprintf(&buf[strlen(buf)], "%d ", o->processor->target->id);
    o->fraction[SCM_MIN] = o->fraction[SCM_MAX] = 1;
  }
  strcat(buf, "]");

  while (tblget(&scm_streams, id = tblgetnexti(&scm_streams, id), &s))
  {
    abortOnError(STREAM(scl.err), s->bytes <= 0);

    s->bandwidth[SCM_MIN] = s->bandwidth[SCM_MAX] = INFINITY;
  }

  /* Setup minimum and maximum usages to best-case and worst-case */
  while (tblget(&scm_procs, id = tblgetnexti(&scm_procs, id), &p))
  {
    while (tblget(&p->operations, id2 = tblgetnexti(&p->operations, id2), &o))
    {
      abortOnError(STREAM(scl.err), o->target_operation->time <= 0);

      o->fraction[SCM_MIN] = 1.0/tblgetelements(&p->operations);
      o->fraction[SCM_MAX] = 1.0;
    }

    while (tblget(&p->streams, id2 = tblgetnexti(&p->streams, id2), &s))
    {
      s->bandwidth[SCM_MIN] = MIN(s->bandwidth[SCM_MIN],
				  1.0/(p->transport_operation->time*
				       tblgetelements(&p->streams)));
      s->bandwidth[SCM_MAX] = MIN(s->bandwidth[SCM_MAX], 1.0/p->transport_operation->time);
    }
  }

  lprintf(STREAM(scl.debug), "Initialized for mapping %s", buf);  
}

void scEvlPropagate(int selector)
{
  int id=-1, id2=-1;
  scm_op_t *o;
  scm_stream_t *s;
  scm_arg_t *a;
  int changed, oldchanged;
  double fraction, bandwidth;

  lprintf(STREAM(scl.crawl), "Propagating flows");

  /* Propagate flow throught the network */

  /* Mark all operations as likely to change */
  while (tblget(&scm_ops, id = tblgetnexti(&scm_ops, id), &o))
    o->state |= SC_EVL_CHANGED;

  /* Mark all streams as likely to change */
  while (tblget(&scm_streams, id = tblgetnexti(&scm_streams, id), &s))
  {
    if (!tblgetelements(&s->processors)) s->bandwidth[selector] = INFINITY;
    s->state |= SC_EVL_CHANGED;    
  }

  do
  {
    changed = 0;

    /* Loop through operations */
    while (tblget(&scm_ops, id = tblgetnexti(&scm_ops, id), &o))
    {
      /* If this operation is mapped, and is likely to change, recompute */
      if (o->processor && (o->state & SC_EVL_CHANGED))
      {
	/* Walk through streams connected to this operation */
	oldchanged = changed;
	while (tblget(&o->streams, id2 = tblgetnexti(&o->streams, id2), &s))
	{
	  /* Calculate the CPU usage based on the stream's bandwidth */
	  fraction = s->bandwidth[selector]/(s->bytes/o->target_operation->time);
	  
	  /* If it is less than it was, update and mark */
	  if (o->fraction[selector] - fraction > SC_EVL_EPSILON)
	  {
//	    printf("op %d lowered fraction from %f to %f\n",
//		   o->id, o->fraction[selector], fraction);
	    o->fraction[selector] = fraction;
	    changed++;
	  }
	}

	/* Mark streams connected to this operation as likely to change */
	if (oldchanged != changed)
	  while (tblget(&o->streams, id2 = tblgetnexti(&o->streams, id2), &s))
	    s->state |= SC_EVL_CHANGED;

	o->state &= ~SC_EVL_CHANGED;
      }
    }

    /* Loop through streams */
    while (tblget(&scm_streams, id = tblgetnexti(&scm_streams, id), &s))
    {
      /* If this stream is likely to change, recompute */
      if (s->state & SC_EVL_CHANGED)
      {
	/* Walk through operations connected to this stream */
	oldchanged = changed;

	a = s->producer;
	do
	{
	  o = a->operation;

	  if (o && o->processor)
	  {
	    /* Calculate the bandwidth based on the operation's CPU usage */
	    bandwidth = o->fraction[selector]*(s->bytes/o->target_operation->time);

	    /* If it is less than it was, update and mark */
	    if (s->bandwidth[selector] - bandwidth > SC_EVL_EPSILON)
	    {
//	      printf("stream %d lowered bandwidth from %20e to %20e (%20e)\n",
//		     s->id, s->bandwidth[selector], bandwidth, 
//		     s->bandwidth[selector] - bandwidth);
	      s->bandwidth[selector] = bandwidth;
	      changed++;
	    }
	  }
	}
	while (tblget(&s->consumers, id2 = tblgetnexti(&s->consumers, id2), &a));

	/* Mark opreations connected to this stream as likely to change */
	if (oldchanged != changed)
	{
	  a = s->producer;
	  do
	  {
	    o = a->operation;

	    if (o)
	      o->state |= SC_EVL_CHANGED;
	  }
	  while (tblget(&s->consumers, id2 = tblgetnexti(&s->consumers, id2), &a));
	}

	s->state &= ~SC_EVL_CHANGED;
      }
    }
  } while (changed);
}

void scEvlBoundMaxUsage(void)
{
  int id=-1, id2=-1;
  scm_proc_t *p;
  scm_op_t *o;
  scm_stream_t *s;
  double fraction, bandwidth;

  lprintf(STREAM(scl.crawl), "Bounding maximum usage");

  /* Give everyone 1 - (summed minimum usage of others) */

  while (tblget(&scm_procs, id = tblgetnexti(&scm_procs, id), &p))
  {
    fraction = 0;
    while (tblget(&p->operations, id2 = tblgetnexti(&p->operations, id2), &o))
      fraction += o->fraction[SCM_MIN];

    while (tblget(&p->operations, id2 = tblgetnexti(&p->operations, id2), &o))
    {
      o->fraction[SCM_MAX] = 1-(fraction-o->fraction[SCM_MIN]);
      lprintf(STREAM(scl.crawl), "Op %d on proc %s now has max fraction %f = 1-(%f-%f)",
              o->id, p->target->name, o->fraction[SCM_MAX], fraction, o->fraction[SCM_MIN]);
    }

    bandwidth = 0;

    while (tblget(&p->streams, id2 = tblgetnexti(&p->streams, id2), &s))
      bandwidth += s->bandwidth[SCM_MIN];

    while (tblget(&p->streams, id2 = tblgetnexti(&p->streams, id2), &s))
    {
      s->bandwidth[SCM_MAX] = (1.0/p->transport_operation->time) - 
	(bandwidth-s->bandwidth[SCM_MIN]);
    }
  }

  lprintf(STREAM(scl.crawl), "Done");
}

void scEvlBoundMinUsage(void)
{
  int id=-1, id2=-1, members, totalmembers, i;
  scm_proc_t *p;
  scm_op_t *o;
  scm_stream_t *s;
  double store, fraction, bandwidth;

  lprintf(STREAM(scl.crawl), "Bounding minimum usage");

  /* Fill everyone to their equal share; what they can't hold, divide equally
   * among the others */

  /* Clear old minimum bandwidths */
  while (tblget(&scm_streams, id = tblgetnexti(&scm_streams, id), &s))
    s->bandwidth[SCM_MIN] = INFINITY;

  while (tblget(&scm_procs, id = tblgetnexti(&scm_procs, id), &p))
  {
    scm_op_t **operations;
    scm_stream_t **streams;

    /* Operations */
    store = 1;
    totalmembers = members = tblgetelements(&p->operations);

    operations = (scm_op_t**) malloc(totalmembers * sizeof(scm_op_t*));

    i = 0;
    while (tblgetnextelement(&p->operations, &id2, &o))
      operations[i++] = o;

    qsort(operations, totalmembers, sizeof(scm_op_t*), scEvlCompareMaxFraction);

    for (i=0; i < totalmembers; i++)
    {
      o = operations[i];

      fraction = MIN(o->fraction[SCM_MAX], store/members);
      o->fraction[SCM_MIN] = fraction;

      lprintf(STREAM(scl.crawl), "Op %d on proc %s now has min fraction %f",
              o->id, p->target->name, o->fraction[SCM_MIN]);

      store -= fraction;
      members--;
    }

    free(operations);

    /* Streams */
    store = 1.0/p->transport_operation->time;
    totalmembers = members = tblgetelements(&p->streams);

    streams = (scm_stream_t**) malloc(totalmembers * sizeof(scm_stream_t*));

    i = 0;
    while (tblgetnextelement(&p->streams, &id2, &s))
      streams[i++] = s;

    qsort(streams, totalmembers, sizeof(scm_stream_t*), scEvlCompareMaxBandwidth);
    
    for (i=0; i < totalmembers; i++)
    {
      s = streams[i];

      bandwidth = MIN(s->bandwidth[SCM_MAX], store/members);
      s->bandwidth[SCM_MIN] = MIN(s->bandwidth[SCM_MIN], bandwidth);

      lprintf(STREAM(scl.crawl), "Stream %d now has min bandwidth %f",
              s->id, s->bandwidth[SCM_MIN]);

      store -= bandwidth;
      members--;
    }

    free(streams);
  }
}

int scEvlCompareMaxFraction(const void* p1, const void *p2)
{
  scm_op_t *o1 = *((scm_op_t**)p1);
  scm_op_t *o2 = *((scm_op_t**)p2);

  if (!o1)
  {
    if (!o2)
    {
      return 0;
    }
    else
    {
      return 1;
    }
  }
  else
  {
    if (!o2)
    {
      return -1;
    }
    else
    {
      if (o1->fraction[SCM_MAX] < o2->fraction[SCM_MAX])
	return -1;
      else if (o1->fraction[SCM_MAX] > o2->fraction[SCM_MAX])
	return 1;
      else
	return 0;
    }
  }
}

int scEvlCompareMaxBandwidth(const void* p1, const void *p2)
{
  scm_stream_t *s1 = *((scm_stream_t**)p1);
  scm_stream_t *s2 = *((scm_stream_t**)p2);

  if (!s1)
  {
    if (!s2)
    {
      return 0;
    }
    else
    {
      return 1;
    }
  }
  else
  {
    if (!s2)
    {
      return -1;
    }
    else
    {
      if (s1->bandwidth[SCM_MAX] < s2->bandwidth[SCM_MAX])
	return -1;
      else if (s1->bandwidth[SCM_MAX] > s2->bandwidth[SCM_MAX])
	return 1;
      else
	return 0;
    }
  }
}

void scEvlPrint(void)
{
  int id=-1, id2=-1, id3=-1;
  scm_proc_t *p;
  scm_op_t *o;
  scm_stream_t *s, *s2;
  char buf[PATH_MAX];
  
  while (tblget(&scm_procs, id = tblgetnexti(&scm_procs, id), &p))
  {
    printf("processor %s\n", p->target->name);
    while (tblget(&p->operations, id2 = tblgetnexti(&p->operations, id2), &o))
    {
      strcpy(buf, "[ ");
      while (tblget(&o->streams, id3 = tblgetnexti(&o->streams, id3), &s))
      {
	if (s->producer && s->producer->operation == o) strcat(buf, "+");
	else                  strcat(buf, "-");
	sprintf(&buf[strlen(buf)], "%d ", s->id);
      }
      strcat(buf, "]");

      if (scs_mapper.evaluator == SC_EVL_UNRELATED || scs_mapper.evaluator == SC_EVL_DEPENDENT)
	printf("  (%3d) %-40s %-15s (line %3d)\n", o->id, o->operation->name, buf,
	       o->operation->line);
      else
	printf("  (%3d) %-40s %-15s (line %3d): %7.3f%% - %7.3f%%\n", o->id, o->operation->name, buf,
	       o->operation->line, o->fraction[SCM_MIN]*100.0, o->fraction[SCM_MAX]*100.0);
    }

    while (tblget(&p->streams, id2 = tblgetnexti(&p->streams, id2), &s))
    {
      if (s->producer)
      {
	id3=-1;
	while (tblget(&s->producer->operation->streams, id3=tblgetnexti(&s->producer->operation->streams, id3), &s2))
	  if (s == s2)
	    break;

	sprintf(buf, "%s(%d).%d", s->producer->operation->operation->name, s->producer->operation->operation->id, id3);
      }
      else
	sprintf(buf, "orphaned stream %d", s->id);

      if (scs_mapper.evaluator == SC_EVL_UNRELATED || scs_mapper.evaluator == SC_EVL_DEPENDENT)
	printf("  (%3d) %-40s\n", s->id, buf);
      else
	printf("  (%3d) %-40s %7.3f - %7.3f Mbps\n", s->id, buf,
	       s->bandwidth[SCM_MIN]/125000.0, s->bandwidth[SCM_MAX]/125000.0);
    }
  }

  if (scs_mapper.evaluator == SC_EVL_UNRELATED)
    printf("Estimated finish time is %f seconds\n", 1.0/scEvlMappingUnrelated());
  else if (scs_mapper.evaluator == SC_EVL_DEPENDENT)
    printf("Estimated finish time is %f seconds\n", 1.0/scEvlMappingDeps(1));
}

void scEvlBackupFractions(void)
{
  int id=-1;
  scm_op_t *o;

  while (tblget(&scm_ops, id = tblgetnexti(&scm_ops, id), &o))
  {
    o->fraction[SCM_OLD_MIN] = o->fraction[SCM_MIN];
    o->fraction[SCM_OLD_MAX] = o->fraction[SCM_MAX];
  }
}

double scEvlCompareFractionsToBackup(void)
{
  int id=-1;
  scm_op_t *o;
  double diff, maxdiff=0;

  while (tblget(&scm_ops, id = tblgetnexti(&scm_ops, id), &o))
  {
    diff = fabs(o->fraction[SCM_OLD_MIN] - o->fraction[SCM_MIN]);
    if (diff > maxdiff) maxdiff = diff;
    diff = fabs(o->fraction[SCM_OLD_MAX] - o->fraction[SCM_MAX]);
    if (diff > maxdiff) maxdiff = diff;
  }

  return maxdiff;
}

double scEvlRootMin(void)
{
  int id=-1;
  double value=0;
  scm_stream_t *s;

  while (tblget(&scm_streams, id = tblgetnexti(&scm_streams, id), &s))
  {
    if (isfinite(s->bandwidth[SCM_MIN]))
      value += sqrt(s->bandwidth[SCM_MIN]);
  }

  return value;
}

double scEvlMappingUnrelated(void)
{
  int id=-1, id2=-1;
  double time, energy=0, maxtime=0, totaltime=0, sqtotaltime=0, resources=!scs_mapper.avgresources;
  double resourcefraction=0, result;
  scm_proc_t *p;
  scm_op_t *o;
  scm_stream_t *s;
  scm_resource_t *r;

  while (tblgetnextelement(&scm_procs, &id, &p))
  {
    time = 0;
    while (tblgetnextelement(&p->operations, &id2, &o))
    {
      time += o->target_operation->time;
      if (o->target_operation->energy > 0)
        energy += o->target_operation->energy;
    }

    while (tblgetnextelement(&p->streams, &id2, &s))
    {
      time += s->bytes * p->transport_operation->time;
      energy += s->bytes * p->transport_operation->energy;
    }

    if (scs_mapper.avgresources)
      while (tblgetnextelement(&p->resources, &id2, &r))
      {
        if (r->target_resource->count)
        {
	  resourcefraction += r->count/r->target_resource->count;
	  resources++;
	}
      }

    totaltime = totaltime + time;
    sqtotaltime = sqtotaltime + time*time;
    if (time > maxtime) maxtime = time;
  }

  totaltime /= tblgetelements(&scm_procs);
  sqtotaltime = sqrt(sqtotaltime)/tblgetelements(&scm_procs);
  if (resources)
    resourcefraction /= resources;

  result = scs_mapper.maxtime*maxtime + scs_mapper.avgtime*totaltime + scs_mapper.avgsqtime*sqtotaltime + scs_mapper.avgenergy*energy + scs_mapper.avgresources*resourcefraction;

  lprintf(STREAM(scl.crawl),
		 "Mapping evaluated to {%f*%f + %f*%f + %f*%f + %f*%f + %f*%f =  %f",
		 scs_mapper.maxtime, maxtime,
		 scs_mapper.avgtime, totaltime,
		 scs_mapper.avgsqtime, sqtotaltime,
		 scs_mapper.avgenergy, energy,
		 scs_mapper.avgresources, resourcefraction,
		 result);

  return 1.0/result;
}
